package com.yun.algorithmproblem.leetcodenotoptimized;

import java.util.ArrayList;
import java.util.HashMap;

public class Leetcode1534 {

	public static void main(String[] args) {
		Leetcode1534 obj=new Leetcode1534();
		obj.countGoodTriplets(new int[]{3,0,1,1,9,7},7,2,3);
	}

	//更好的方案，前缀和

	public int countGoodTriplets(int[] arr, int a, int b, int c) {
		int ans=0;
		HashMap<Integer, ArrayList<Integer>> map=new HashMap<>();
		for (int i = 1; i < arr.length-1; i++) {
			ArrayList<Integer> nums = new ArrayList<>();
			for (int j = i+1; j < arr.length; j++) {
				if(Math.abs(arr[i]-arr[j])<=b){
					nums.add(j);
				}
			}
			map.put(i,nums);
		}
		for (int i = 0; i < arr.length-2; i++) {
			for (int j = i+1; j < arr.length-1; j++) {
				if(Math.abs(arr[i]-arr[j])>a){
					continue;
				}
				ArrayList<Integer> nums = map.get(j);
				for (Integer num : nums) {
					if(Math.abs(arr[i]-arr[num])<=c){
						ans++;
					}
				}
			}
		}
		return ans;
	}
}
